package com.linchong.sort;

/**
 * @BelongsProject:Algorithm
 * @BelongsPackage:com.linchong.sort
 * @Author:linchong
 * @CreateTime:2019-01-04 22:09
 * @Description:插入排序
 * 思路：双重循环，一层取值插入元素，一层比较寻找位置
 * 步骤：取元素，移动元素，找位置，插入
 * 最好时间复杂度：O(n)
 * 最坏时间复杂度：O(n*n)
 * 平均时间复杂度：O(n*n)
 * 空间复杂度：O(1)
 * 是否稳定：稳定
 * 是否受初始化数据影响：受
 *
 */
public class InsertionSort {
    public static void insertionSort(int[] arr,int n){
        int i,j;
        for(i=1;i<n;i++){
            int val = arr[i];//待插入数据
            j = i-1;//要插入的位置
            for(;j>=0;j--){
                if(arr[j]>val){
                    arr[j+1] = arr[j]; //移动数据
                }else {
                    break;
                }
            }
            arr[j+1] = val;
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,4,2,6,8,12,9};
        insertionSort(arr,arr.length);
        for (int i : arr) {
            System.out.print(" " + i);
        }
    }
}
